競プロ典型 90 問 013
(工事中)
解き方
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
typedef struct list {
int op;
int cost;
struct list *next;
} list;
int used = 0;
void down_heap (int i, int num_elem, int *pri_queue, int *val, int* map) {
if (num_elem <= 2*i+1) {
return;
}
if (num_elem > 2*i+2) {
}
if (ch0 < ch1 && ch0 < val[pri_queuei]) { map[pri_queue2*i+1] = 2*i+1; down_heap (2*i+1, num_elem, pri_queue, val, map);
} else if (ch1 < val[pri_queuei]) { map[pri_queue2*i+2] = 2*i+2; down_heap (2*i+2, num_elem, pri_queue, val, map);
}
return;
}
void up_heap (int i, int *pri_queue, int *val, int *map) {
int parent = (i - 1) / 2;
if (i == 0) {
return;
}
if (val[pri_queuei] < val[pri_queueparent]) { map[pri_queueparent] = parent; up_heap (parent, pri_queue, val, map);
}
return;
}
int dequeue(int *num_elem, int *pri_queue, int *val, int* map) {
*num_elem -= 1;
down_heap(0, *num_elem, pri_queue, val, map);
return ans;
}
void dijkstra(int *num_elem, int *pri_queue, int *d, int* map, list **e) {
while (*num_elem > 0) {
int v = dequeue(num_elem, pri_queue, d, map);
while (l != NULL) {
int tmp_d = dv + l->cost; up_heap(mapl->op-1, pri_queue, d, map); }
l = l->next;
}
}
return;
}
int main () {
int n = 0;
int m = 0;
int res = 0;
int num_elem = 0;
res = scanf("%d", &n);
res = scanf("%d", &m);
for (int i = 0; i < m; i++) {
int a = 0;
int b = 0;
int c = 0;
res = scanf("%d", &a);
res = scanf("%d", &b);
res = scanf("%d", &c);
used++;
used++;
}
for (int i = 0; i < n; i++) {
num_elem++;
}
dijkstra(&num_elem, pri_queue, d1, map, e);
num_elem = 1;
for (int i = 0; i < n - 1; i++) {
num_elem++;
}
dijkstra(&num_elem, pri_queue, dn, map, e);
for (int i = 0; i < n; i++) {
}
return 0;
}
私の提出一覧
table: submissions_atcoder_typical90_013
提出のURL 提出時刻 結果 備考
感想
ローカルにおいてあったzakkan.txt（雑感）には、まだ書かれていないので、こっちに直接書く
この問題も提出回数が多いな…
ダイクストラ法自体は大学の演習で書いたことあるし、動作もそこまで複雑じゃないからイメージしやすいんやけど、そのときは$ V^{2} のオーダーの計算量で許されていたから、優先度付きキューを使う
ダイクストラ法自体は大学の演習で書いたことあるし、動作もそこまで複雑じゃないからイメージしやすいんやけど、そのときは$ V^{2} のオーダーの計算量で許されていたから、優先度付きキューは使っていなかった
いざ優先度付きキューを使って実装してみたら、距離が更新されたときにキューにすでにいれた値をどうすればよいかが悩ましかった。
いまでこそ、すでに入れたのはそのままおいておいて、改めて入れても問題ないことを知ったからそうしているけれど、当時はそんな発想はなかったため、キューに入れた値を書き換えることをしていた。
そもそも$ E の個数は$ O(V^{2}) なので、疎なグラフという前提がなければ$ V^{2} より速くすることを求められることもないし
そんなこんなで、キュー周りの実装がややこしくなったので、それで間違いを作ってしまったのかなと思ったが、提出を追ってみても原因が何だったのか思い出せなかった。
ただ、いったん止めて次の日から（13回目以降）は、いろいろ提出してみて、どこが悪いか探そうとしている感じやね。だから提出回数も増えていったのかな。
基本的に私は入力例でテストするから、それは合っているのにACにならない場合はどの例をテストすべきかもわからず、たまにこうやってハマることもあるんやおね